{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryNode:\n",
    "    indent = \"  \"\n",
    "\n",
    "    def __init__(self, value) -> None:\n",
    "        self.value = value\n",
    "        self.left_child = None\n",
    "        self.right_child = None\n",
    "\n",
    "    def add_left(self, new_node):\n",
    "        self.left_child = new_node\n",
    "\n",
    "    def add_right(self, new_node):\n",
    "        self.right_child = new_node\n",
    "\n",
    "    def __str__(self, level = 0):\n",
    "        result = f'{self.value}:\\n'\n",
    "        level += 1\n",
    "        \n",
    "        if (self.left_child == None and self.right_child == None):\n",
    "            return result\n",
    "\n",
    "        if (self.left_child == None):\n",
    "            result += f'{self.indent * level}None\\n'\n",
    "        else:\n",
    "            result += f'{self.indent * level}{self.left_child.__str__(level)}'\n",
    "\n",
    "        if (self.right_child == None):\n",
    "            result += f'{self.indent * level}None\\n'\n",
    "        else:\n",
    "            result += f'{self.indent * level}{self.right_child.__str__(level)}'\n",
    "            \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In general, when you work with recursive methods, the method should think about two things when it visits a node. **First, what should the method do for this node? Second, what should the method do for the node’s children?**\n",
    "\n",
    "Many tree algorithms move recursively down through the tree and stop when they reach leaf nodes, which have no children to recurse down further. (Some algorithms work the other way around, moving from a leaf node upward through the tree until they reach the root. Our node classes aren’t set up for that because the nodes don’t have links to their parents.)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Build a test tree.\n",
    "#      Root\n",
    "#      /  \\\n",
    "#     A    B\n",
    "#    / \\    \\\n",
    "#   C   D    E\n",
    "#           /\n",
    "#          F\n",
    "root_node = BinaryNode(\"Root\")\n",
    "a_node = BinaryNode(\"A\")\n",
    "b_node = BinaryNode(\"B\")\n",
    "c_node = BinaryNode(\"C\")\n",
    "d_node = BinaryNode(\"D\")\n",
    "e_node = BinaryNode(\"E\")\n",
    "f_node = BinaryNode(\"F\")\n",
    "\n",
    "root_node.add_left(a_node)\n",
    "root_node.add_right(b_node)\n",
    "a_node.add_left(c_node)\n",
    "a_node.add_right(d_node)\n",
    "b_node.add_right(e_node)\n",
    "e_node.add_left(f_node)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Root:\n",
      "  A:\n",
      "    C:\n",
      "    D:\n",
      "  B:\n",
      "    None\n",
      "    E:\n",
      "      F:\n",
      "      None\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(root_node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A:\n",
      "  C:\n",
      "  D:\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(a_node)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "e63faaf9bc27d837377622cad56f3d439b9a97e8fa476559128293c868ce68e0"
  },
  "kernelspec": {
   "display_name": "Python 3.9.7 64-bit ('word_database': conda)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
